package com.sise.Backtracking;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *      17. 电话号码的字母组合
 *
 *      给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *      给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 *      输入：digits = "23"
 *      输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 *      思路：
 *          一开始知道用回溯算法，但对于具体数字所对应的 数值遍历 没有具体思路。
 *          在实际的解决中需要使用 Map 进行存储映射，value 中存储多种可能，digits 中包含多个 key，这里使用的是 index 进行叠加
 *          这里的撤回和选择，是 value 中的数值 (遍历)，
 *
 *          这道题是不同集合之间的组合问题，首先根据 depth 树深度来确定使用不同的值，例如初始深度为 0，那么 2 = digits.charAt(0)，
 *          再根据 Map 确定号码 2 所代表的英文字母，再对其字母进行遍历取值操作
 *
 *
 *          因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合。
 *          而组合I、组合III 都是是求同一个集合中的组合！
 */
public class _17_letterCombinations {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() == 0) return result;

        Map<Character, String> phoneMap = new HashMap<Character, String>() {
            {
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }
        };
        backTrack(result, phoneMap, digits, 0, new StringBuffer());
        return result;
    }

    private void backTrack(List<String> result, Map<Character, String> phoneMap, String digits, int depth, StringBuffer path) {

        // 如果当前 depth 索引等于 字符串长度，或代表的是递归树的深度，那么说明回溯已经遍历完毕
        if (depth == digits.length()) {
            result.add(path.toString());
            return;
        }

        // 假设 digits 代表 '23'，depth 代表当前位置，depth 默认为 0，也就是默认为 2 = digits.charAt(0);
        // 这里先拿到第 i 位的 key，然后对 key 进行遍历，在遍历中直接 递归 调用(因为每个 key 只能够用一次)，对于下个 key 使用的是 depth + 1。
        // 如果进行撤回操作，那么撤回的也是 value 值，而不是 key 值
        // key 代表电话号码，value 代表此号码下的英文字符串
        char digit = digits.charAt(depth);
        String letters = phoneMap.get(digit);
        int lettersCount = letters.length();
        for (int i = 0; i < lettersCount; i++) {
            path.append(letters.charAt(i));
            backTrack(result, phoneMap, digits, depth + 1, path);
            path.deleteCharAt(depth);
        }
    }
}
